翻訳と辞書 Words near each other ・ Griffin Technology (Diebold subsidiary) ・ Griffin Television Tower Oklahoma ・ Griffin Theatre Company ・ Griffin Township, Pope County, Arkansas ・ Griffin v. California ・ Griffin v. County School Board of Prince Edward County ・ Griffin v. Illinois ・ Griffin v. Maryland ・ Griffin's Foods ・ Griffin's Hill ・ Griffin's leaf-nosed bat ・ Grieshorn ・ Griesingen ・ Grieskirchen ・ Grieskirchen District ・ Griesmer bound ・ Griess algebra ・ Griess test ・ Griessee ・ Griesstätt ・ Griest ・ Griet ・ Grietenij ・ Griethausen ・ Grietje Jansen-Anker ・ Grietje Staffelt ・ Grietje Vanderheijden ・ Grietman ・ Grievance ・ Grievance (disambiguation) Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Griesmer bound ： ウィキペディア英語版 Griesmer bound In the mathematics of coding theory, the Griesmer bound, named after James Hugo Griesmer, is a bound on the length of binary codes of dimension ''k'' and minimum distance ''d''. There is also a very similar version for non-binary codes. == Statement of the bound == For a binary linear code, the Griesmer bound says: : $n\backslash geq\; \backslash sum\_^\; \backslash left\backslash lceil\backslash frac\backslash right\backslash rceil.$ == Proof== Let $N(k,d)$ denote the minimum length of a binary code of dimension ''k'' and distance ''d''. Let ''C'' be such a code. We want to show that $N(k,d)\backslash geq\; \backslash sum\_^\; \backslash left\backslash lceil\backslash frac\backslash right\backslash rceil$. Let ''G'' be a generator matrix of ''C''. We can always suppose that the first row of ''G'' is of the form ''r'' = (1, ..., 1, 0, ..., 0) with weight ''d''. : $G=\; \backslash begin$ 1 & \dots & 1 & 0 & \dots & 0 \\ \ast & \ast & \ast & & G' & \\ \end The matrix G' generates a code C', which is called the residual code of C. C' has obviously dimension $k\text{'}=k-1$ and length $n\text{'}=N(k,d)-d$. C' has a distance d', but we don't know it. Let $u\backslash in\; C^$ s.t. $w(u)=d\text{'}$. There exists a vector $v\backslash in\; (F\_2)^d$ s.t. the concatenation $(v|u)\backslash in\; C$. Then $w(v)+w(u)=w(v|u)\backslash geq\; d$. On the other hand, also $(v|u)+r\backslash in\; C$, since $r\backslash in\; C$ and $C$ is linear, so $w((v|u)+r)\backslash geq\; d$. But $w((v|u)+r)=w(((1,1,...,1)+v)|u)=d-w(v)+w(u)$, so this becomes $d-w(v)+w(u)\backslash geq\; d$. By summing this with $w(v)+w(u)\backslash geq\; d$, we obtain $d+2w(u)\backslash geq\; 2d$. But $w(u)=d\text{'}$, so we get $d\text{'}\backslash geq\; d/2$. This implies $n\text{'}\backslash geq\; N(k-1,d/2)$, therefore $n\text{'}\backslash geq\; \backslash left\backslash lceil\; N(k-1,d/2)\backslash right\backslash rceil$ (due to the integrality of n'), so that $N(k,d)\backslash geq\; \backslash left\backslash lceil\; N(k-1,d/2)\backslash right\backslash rceil\; +d$. By induction over ''k'' we will eventually get $N(k,d)\backslash geq\; \backslash sum\_^\; \backslash left\backslash lceil\backslash frac\backslash right\backslash rceil$ (note that at any step the dimension decreases by 1 and the distance is halved, and we use the identity $\backslash left\backslash lceil\backslash frac\backslash right\backslash rceil\; =\; \backslash left\backslash lceil\backslash frac\backslash right\backslash rceil$ for any integer ''a'' and positive integer ''k''). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Griesmer bound」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.